"""《Dijkstra算法程序》
    时间：2025.03.06
    作者：不去幼儿园
"""
import heapq


def dijkstra(graph, start):
	-distances = {vertex: float('infinity') for vertex in graph}
	distances[start] = 0
	-previous_nodes = {vertex: None for vertex in graph}
	-unvisited_queue = [(0, start)]

	while unvisited_queue:
		current_distance, current_vertex = heapq.heappop(unvisited_queue)

		if current_distance > distances[current_vertex]:
			continue

		for neighbor, weight in graph[current_vertex].items():
			distance = current_distance + weight

			if distance < distances[neighbor]:
				distances[neighbor] = distance
				previous_nodes[neighbor] = current_vertex
				heapq.heappush(unvisited_queue, (distance, neighbor))

	return distances, previous_nodes


# Example graph represented as an adjacency list
graph = {
	'A': {'B': 2, 'C': 3},
	'B': {'A': 2, 'C': 1, 'D': 4},
	'C': {'A': 3, 'B': 1, 'D': 5},
	'D': {'B': 4, 'C': 5}
}

start_vertex = 'A'
distances, previous_nodes = dijkstra(graph, start_vertex)


# Function to print the shortest path from start_vertex to end_vertex
def print_shortest_path(previous_nodes, start_vertex, end_vertex):
	path = []
	current_vertex = end_vertex
	while current_vertex is not None and current_vertex != start_vertex:
		path.insert(0, current_vertex)
		current_vertex = previous_nodes[current_vertex]
	if current_vertex is None:
		return "Path does not exist"
	else:
		path.insert(0, start_vertex)
		return path


# Output the results
print("Vertex\tDistance\tPath")
for vertex in graph:
	if vertex != start_vertex:
		dist = distances[vertex]
		path = print_shortest_path(previous_nodes, start_vertex, vertex)
		print(f"{vertex}\t{dist}\t\t{path}")
